package main

import (
	"fmt"
	. "local/algorithm/util"
	"strconv"
)

/**
你需要从一个包括括号和整数的字符串构建一棵二叉树。

输入的字符串代表一棵二叉树。它包括整数和随后的0，1或2对括号。整数代表根的值，一对括号内表示同样结构的子树。

若存在左子结点，则从左子结点开始构建。

示例:

输入: "4(2(3)(1))(6(5))"
输出: 返回代表下列二叉树的根节点:

       4
     /   \
    2     6
   / \   /
  3   1 5

第一眼看到'('等符号时，就自然联想到使用stack，此类题目一般采用遍历+stack解决

按字符遍历
	当字符为)时，
		弹出stack，保障栈顶始终是下一个元素父节点
	当前位置字符为1~9或-时，
		从当前位置向后找最大合法数值并以此值构造新树节点，
		插入节点:如果存在父节点(即stack中节点数>0)，连接父节点(stack顶元素)与新节点(左结点不存在为左节点，左节点存在为右节点)
		入栈

字符串为前序遍历的值
*/

func main() {
	s := "4(2(3)(1))(6(5))"
	t := str2tree(s)
	fmt.Println(t)
}

func str2tree(s string) *TreeNode {

	if 0 == len(s) {
		return nil
	}
	//初始化栈，其中存放的节点指针
	stack := []*TreeNode{}
	for i := 0; i < len(s); i++ {
		if s[i] == ')' {
			stack = stack[:len(stack)-1]
		} else if (s[i] >= '0' && s[i] <= '9') || s[i] == '-' { //当前位是0~9或-时，开启记录数字
			j := i
			for i+1 < len(s) && s[i+1] >= '0' && s[i+1] <= '9' { //数字后续由0~9组成时，继续扩展数字长度 且注意要先判断i+1<len(s)保证i有效
				i++
			}
			v, _ := strconv.Atoi(s[j : i+1]) //注意这里是i+1
			n := &TreeNode{Val: v}
			if 0 != len(stack) { //len(stack)!=0表示存在对于父节点的记录，非首次数字比较
				parent := stack[len(stack)-1] //取出当前节点的父节点
				if nil == parent.Left {
					parent.Left = n
				} else {
					parent.Right = n
				}
			}
			stack = append(stack, n)
		}
	}
	return stack[len(stack)-1] //在此就是stack[0]
}

func str2tree(s string) *TreeNode {
	if len(s) == 0 {
		return nil
	}
	stack := []*TreeNode{}
	for i := 0; i < len(s); i++ {
		if s[i] == ')' {
			stack = stack[:len(stack)-1]
		} else if (s[i] >= '0' && s[i] <= '9') || s[i] == '-' {
			j := i
			for i+1 < len(s) && s[i+1] >= '0' && s[i+1] <= '9' {
				i++
			}
			v, _ := strconv.Atoi(s[j : i+1])
			n := &TreeNode{Val: v}
			if 0 != len(stack) {
				parent := stack[len(stack)-1]
				if nil == parent.Left {
					parent.Left = n
				} else {
					parent.Left = n
				}
			}
			stack = append(stack, n)
		}
	}
	return stack[len(stack)-1]
}
